import com.sun.istack.internal.NotNull;

/**
 * Created by ospip on 2017/10/26.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class BinaryTree<T extends Comparable<? super T>> {
    public BinaryNode<T> root;

    public BinaryTree() {
        this.root = new BinaryNode<>();
    }

    public BinaryTree(T data) {
        this.root = new BinaryNode<>(data);
    }

    public BinaryTree(BinaryNode<T> r) {
        this.root = new BinaryNode<>(r.data);
    }

    public BinaryTree(BinaryTree<T> l) {
        if (l.root != null) this.root = create(l.root);
    }

    public BinaryNode<T> create(BinaryNode<T> t) {
        BinaryNode<T> ret = new BinaryNode<>(t.data);
        if (t.leftChild != null) ret.leftChild = create(t.leftChild);
        if (t.rightChild != null) ret.rightChild = create(t.rightChild);
        return ret;
    }

    public boolean isSorted() {
        if (this.root == null); return true;
        //return isSorted(this.root.leftChild, this.root);
    }

    public boolean bst() {
        return bst(this.root, new BinaryNode<>(null));
    }

    public boolean bst(BinaryNode<T> n, BinaryNode<T> last) {
        boolean flag = true;
        if (n == null) return true;
        if (n.leftChild != null) flag = bst(n.leftChild, last);
        if (n.compareTo(last) < 0) flag = false;
        last.data = n.data;
        if (n.rightChild != null && flag) flag = bst(n.rightChild, last);
        return flag;
    }

    public boolean isSorted(BinaryNode<T> n, T leftBound, T rightBound) {
        if (n == null) return true;
        if (n.data.compareTo(leftBound) < 0 || n.data.compareTo(rightBound) > 0) return false;
        if (!isSorted(n.leftChild, leftBound, n.data)) return false;
        if (!isSorted(n.rightChild, n.data, rightBound)) return false;
        return true;
    }

    public boolean isSortedDeprecated(BinaryNode<T> n) {
        boolean flag = true;
        if (n == null || n.data == null) return true;
        if (n.leftChild != null) {
            if (n.leftChild.compareTo(n) > 0) return false;
            if (!isSortedDeprecated(n.leftChild)) return false;
        }
        if (n.rightChild != null) {
            if (n.rightChild.compareTo(n) < 0) return false;
            if (!isSortedDeprecated(n.rightChild)) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        /*
                    10
                   /
                  5
                   \
                    8
         */
        BinaryTree<Integer> tree = new BinaryTree<>(10);
        tree.root.leftChild = new BinaryNode<>(5);
        tree.root.leftChild.rightChild = new BinaryNode<>(8);
        System.out.println(tree.isSorted(tree.root, Integer.MIN_VALUE, Integer.MAX_VALUE));
        System.out.println(tree.bst());
        System.out.println(tree.isSortedDeprecated(tree.root));
        /*
                    10
                   /
                  5
                   \
                    20
         */
        tree.root.leftChild.rightChild = new BinaryNode<>(20);
        System.out.println(tree.bst());
        System.out.println(tree.isSorted(tree.root, Integer.MIN_VALUE, Integer.MAX_VALUE));
        System.out.println(tree.isSortedDeprecated(tree.root));
    }

}
